{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Add Two Numbers II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #linked-list #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #链表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addTwoNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两数相加 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个 <strong>非空 </strong>链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。</p>\n",
    "\n",
    "<p>你可以假设除了数字 0 之外，这两个数字都不会以零开头。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626420025-fZfzMX-image.png\" style=\"width: 302px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [7,2,4,3], l2 = [5,6,4]\n",
    "<strong>输出：</strong>[7,8,0,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [2,4,3], l2 = [5,6,4]\n",
    "<strong>输出：</strong>[8,0,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [0], l2 = [0]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表的长度范围为<code> [1, 100]</code></li>\n",
    "\t<li><code>0 &lt;= node.val &lt;= 9</code></li>\n",
    "\t<li>输入数据保证链表代表的数字无前导 0</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果输入链表不能翻转该如何解决？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [add-two-numbers-ii](https://leetcode.cn/problems/add-two-numbers-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [add-two-numbers-ii](https://leetcode.cn/problems/add-two-numbers-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,2,4,3]\\n[5,6,4]', '[2,4,3]\\n[5,6,4]', '[0]\\n[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = dummy = ListNode()  # 哨兵节点\n",
    "        carry = 0  # 进位\n",
    "        while l1 or l2 or carry:  # 有一个不是空节点，或者还有进位，就继续迭代\n",
    "            if l1: carry += l1.val  # 节点值和进位加在一起\n",
    "            if l2: carry += l2.val  # 节点值和进位加在一起\n",
    "            cur.next = ListNode(carry % 10)  # 每个节点保存一个数位\n",
    "            carry //= 10  # 新的进位\n",
    "            cur = cur.next  # 下一个节点\n",
    "            if l1: l1 = l1.next  # 下一个节点\n",
    "            if l2: l2 = l2.next  # 下一个节点\n",
    "        return dummy.next  # 哨兵节点的下一个节点就是头节点\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)  # l1 和 l2 反转后，就变成【2. 两数相加】了\n",
    "        l3 = self.addTwo(l1, l2)\n",
    "        return self.reverseList(l3)  # 计算完毕后再反转\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse_list(head):\n",
    "            if head.next==None:\n",
    "                return head\n",
    "            current=head\n",
    "            parent= None\n",
    "            while(current is not None):\n",
    "                temp=current.next\n",
    "                current.next=parent\n",
    "                parent=current\n",
    "                current=temp\n",
    "            return parent\n",
    "\n",
    "        l1_rev=reverse_list(l1)\n",
    "        l2_rev=reverse_list(l2)\n",
    "        carry=0\n",
    "        res_head=ListNode()\n",
    "        res_current=res_head\n",
    "        l1_current=l1_rev\n",
    "        l2_current=l2_rev\n",
    "\n",
    "        while l1_current is not None or l2_current is not None or carry!=0:\n",
    "            if l1_current is not None:\n",
    "                l1_num=l1_current.val\n",
    "                l1_current=l1_current.next\n",
    "            else:\n",
    "                l1_num=0\n",
    "            if l2_current is not None:\n",
    "                l2_num=l2_current.val\n",
    "                l2_current=l2_current.next\n",
    "            else:\n",
    "                l2_num=0                \n",
    "            res_current.val=(l1_num+l2_num+carry)%10\n",
    "            carry= int((l1_num+l2_num+carry)/10)\n",
    "            if l1_current is not None or l2_current is not None or carry!=0:\n",
    "                res_current.next=ListNode()\n",
    "                res_current=res_current.next\n",
    "            else:\n",
    "                tail=res_current\n",
    "        res_head = reverse_list(res_head)\n",
    "        return res_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "# 使用栈时间复杂度，空间复杂度都为0(m+n)\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1:\n",
    "            stack1.append(l1)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        carry = 0 \n",
    "        sum = 0\n",
    "        node = None\n",
    "        pre = None\n",
    "        while stack1 or stack2:\n",
    "            if not stack1:\n",
    "                val1 = 0\n",
    "                node = stack2[-1]\n",
    "            else:\n",
    "                node = stack1.pop()\n",
    "                val1 = node.val\n",
    "\n",
    "            if not stack2:\n",
    "                val2 = 0\n",
    "            else:\n",
    "                val2 = stack2.pop().val\n",
    "\n",
    "            sum = (val1 + val2 + carry)%10\n",
    "            carry = (val1 + val2 + carry)//10\n",
    "\n",
    "            node.val = sum\n",
    "            node.next = pre\n",
    "            pre = node\n",
    "        \n",
    "        if carry!=0:\n",
    "            node = ListNode()\n",
    "            node.val = 1\n",
    "            node.next = pre\n",
    "\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        listA = list()\n",
    "        listB = list()\n",
    "        while l1:\n",
    "            listA.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            listB.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        ans_list = list()\n",
    "        sum_up = 0\n",
    "        while listA or listB:\n",
    "            a = 0 if not listA else listA.pop()\n",
    "            b = 0 if not listB else listB.pop()\n",
    "            ans_list.append((a+b+sum_up) % 10)       # sum_up放在里面，防止连续进位\n",
    "            sum_up = (a+b+sum_up) // 10\n",
    "        \n",
    "\n",
    "        if sum_up:\n",
    "            ans_list.append(1)           # 5+5的场景\n",
    "\n",
    "        \n",
    "        ans = ListNode(ans_list.pop())\n",
    "        prev = ans\n",
    "        while ans_list:\n",
    "            prev.next = ListNode(ans_list.pop())   # 需要创建下个节点，创建当前节点的话会多一个next\n",
    "            prev = prev.next\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1,s2=[],[]\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1=l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2=l2.next\n",
    "        ans=None\n",
    "        carry=0    \n",
    "        while s1 or s2 or carry!=0:\n",
    "            a=0 if not s1 else s1.pop()\n",
    "            b=0 if not s2 else s2.pop() \n",
    "            cur=a+b+carry\n",
    "            carry=cur//10\n",
    "            cur %=10\n",
    "            curnode=ListNode(cur)\n",
    "            curnode.next=ans\n",
    "            ans=curnode\n",
    "        return ans    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(head):\n",
    "            tail = None\n",
    "            cur = head\n",
    "            while cur is not None:\n",
    "                next = cur.next\n",
    "                cur.next = tail\n",
    "                tail = cur\n",
    "                cur = next\n",
    "            return tail\n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        carry = 0\n",
    "        ans = ListNode(0)\n",
    "        cur = ans\n",
    "        while l1 or l2 or carry != 0:\n",
    "            l1v = l1.val if l1 is not None else 0\n",
    "            l2v = l2.val if l2 is not None else 0\n",
    "            s = l1v + l2v + carry\n",
    "            cur.next = ListNode(s % 10)\n",
    "            cur = cur.next\n",
    "            carry = s // 10\n",
    "            if l1 is not None:\n",
    "                l1 = l1.next \n",
    "            if l2 is not None:\n",
    "                l2 = l2.next\n",
    "        return reverse(ans.next)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        dummy = ListNode()\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry:\n",
    "            s = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry\n",
    "            carry, val = divmod(s, 10)\n",
    "            dummy.next = ListNode(val, dummy.next)\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reserve(root):\n",
    "            pre = None\n",
    "            while root:\n",
    "                tmp = root.next\n",
    "                root.next = pre\n",
    "                pre = root\n",
    "                root = tmp\n",
    "            return pre\n",
    "        l1 = reserve(l1)\n",
    "        l2 = reserve(l2)\n",
    "        s = ListNode(0)\n",
    "        r = s\n",
    "        flag = 0\n",
    "        while l1 and l2:\n",
    "            cur = l1.val + l2.val + flag\n",
    "            s.next = ListNode(cur%10)\n",
    "            flag = cur//10\n",
    "            s = s.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        while l1:\n",
    "            cur = l1.val + flag\n",
    "            s.next = ListNode(cur%10)\n",
    "            flag = cur//10\n",
    "            s = s.next\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            cur = l2.val + flag\n",
    "            s.next = ListNode(cur%10)\n",
    "            flag = cur//10\n",
    "            s = s.next\n",
    "            l2 = l2.next\n",
    "        if flag > 0:\n",
    "            s.next = ListNode(flag)\n",
    "        return reserve(r.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def calc(node):\n",
    "            ans = 0\n",
    "            while node:\n",
    "                ans = ans*10\n",
    "                ans += node.val\n",
    "                node = node.next\n",
    "            return ans\n",
    "        n1 = calc(l1)\n",
    "        n2 = calc(l2)\n",
    "        he = n1+n2\n",
    "        strhe = str(he)\n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        for i in range(len(strhe)):\n",
    "            node = ListNode(int(strhe[i]))\n",
    "            p.next = node\n",
    "            p = p.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack_1 = []\n",
    "        stack_2 = []\n",
    "        while l1:\n",
    "            stack_1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        while l2:\n",
    "            stack_2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        following = None\n",
    "        carry = 0\n",
    "        while stack_1 or stack_2 or carry != 0:\n",
    "            num_1 = stack_1.pop() if stack_1 else 0\n",
    "            num_2 = stack_2.pop() if stack_2 else 0\n",
    "            temp = (carry + num_1 + num_2) % 10\n",
    "            carry = (carry + num_1 + num_2) // 10\n",
    "            curr = ListNode(temp)\n",
    "            curr.next = following\n",
    "            following = curr\n",
    "\n",
    "        return following"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack_1 = []\n",
    "        stack_2 = []\n",
    "        while l1:\n",
    "            stack_1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        while l2:\n",
    "            stack_2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        following = None\n",
    "        carry = 0\n",
    "        while stack_1 or stack_2 or carry != 0:\n",
    "            num_1 = stack_1.pop() if stack_1 else 0\n",
    "            num_2 = stack_2.pop() if stack_2 else 0\n",
    "            temp = (carry + num_1 + num_2) % 10\n",
    "            carry = (carry + num_1 + num_2) // 10\n",
    "            curr = ListNode(temp)\n",
    "            curr.next = following\n",
    "            following = curr\n",
    "        \n",
    "        # if carry:\n",
    "        #     curr = ListNode(carry)\n",
    "        #     curr.next = following\n",
    "        #     following = curr\n",
    "\n",
    "        return following"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "  def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "    cur, pre = head, None\n",
    "    while cur:\n",
    "      temp = cur.next\n",
    "      cur.next = pre\n",
    "      pre = cur\n",
    "      cur = temp\n",
    "    return pre\n",
    "  def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "    l1, l2 = self.reverseList(l1), self.reverseList(l2)\n",
    "    cur = dummy = ListNode()\n",
    "    carry = 0\n",
    "\n",
    "    while l1 or l2 or carry:\n",
    "      carry += (l1.val if l1 else 0) + (l2.val if l2 else 0) \n",
    "      cur.next = ListNode(carry % 10)\n",
    "      carry //= 10\n",
    "      cur = cur.next\n",
    "      \n",
    "      if l1: l1 = l1.next\n",
    "      if l2: l2 = l2.next\n",
    "\n",
    "    return self.reverseList(dummy.next)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "from typing import Optional\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def get_n(l):\n",
    "            n = 0\n",
    "            while l is not None:\n",
    "                n *= 10\n",
    "                n += l.val\n",
    "                l = l.next\n",
    "            return n\n",
    "        n1 = get_n(l1)\n",
    "        n2 = get_n(l2)\n",
    "\n",
    "        head = ListNode()\n",
    "        cur = head\n",
    "        n = n1 + n2\n",
    "        val_list = [int(c) for c in str(n)]\n",
    "        for v in val_list:\n",
    "            cur.next = ListNode(val = v)\n",
    "            cur = cur.next\n",
    "\n",
    "        return head.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def rever(l: Optional[ListNode]) -> Optional[ListNode]:\n",
    "    head = ListNode(next=l)\n",
    "    cur = l.next\n",
    "    while cur:\n",
    "        l.next = cur.next\n",
    "        cur.next = head.next\n",
    "        head.next = cur\n",
    "        cur = l.next\n",
    "    return head.next\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        \n",
    "        #先全部逆置\n",
    "        #然后从低位到高位进行加和进位\n",
    "        #7 2 4 3\n",
    "        #  5 6 4\n",
    "        #=>\n",
    "        #3 4 2 7\n",
    "        #4 6 5\n",
    "        more = 0\n",
    "        l1 = rever(l=l1)\n",
    "        l2 = rever(l=l2)\n",
    "        res_head = ListNode(next=None)\n",
    "        while l1 and l2:\n",
    "            #head insert\n",
    "            sum = l1.val + l2.val + more\n",
    "            node = ListNode(val=sum % 10, next=res_head.next)\n",
    "            res_head.next = node\n",
    "            if sum >= 10:\n",
    "                more = 1\n",
    "            else:\n",
    "                more = 0\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        if l1:\n",
    "            while l1:\n",
    "                sum = l1.val + more\n",
    "                node = ListNode(val=sum % 10, next=res_head.next)\n",
    "                res_head.next = node\n",
    "                if sum >= 10:\n",
    "                    more = 1\n",
    "                else:\n",
    "                    more = 0\n",
    "                l1 = l1.next\n",
    "            if more == 1:\n",
    "                node = ListNode(val=1, next=res_head.next)\n",
    "                res_head.next = node\n",
    "        elif l2:\n",
    "            while l2:\n",
    "                sum = l2.val + more\n",
    "                node = ListNode(val=sum % 10, next=res_head.next)\n",
    "                res_head.next = node\n",
    "                if sum >= 10:\n",
    "                    more = 1\n",
    "                else:\n",
    "                    more = 0\n",
    "                l2 = l2.next\n",
    "            if more == 1:\n",
    "                node = ListNode(val=1, next=res_head.next)\n",
    "                res_head.next = node\n",
    "        else:\n",
    "            if more == 1:\n",
    "                node = ListNode(val=1, next=res_head.next)\n",
    "                res_head.next = node\n",
    "        return res_head.next\n",
    "        #或者把两个数提出来相加得到结果\n",
    "        #然后转化为链表\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1, n1 = self.reverse(l1)\n",
    "        l2, n2 = self.reverse(l2)\n",
    "        if n1 < n2:\n",
    "            l1, l2 = l2, l1\n",
    "        r = 0\n",
    "        head = l1\n",
    "        while l1:\n",
    "            l2_val = l2.val if l2 else 0\n",
    "            # print(l1.val, /l2_val, r)\n",
    "            l1.val = l1.val + l2_val + r\n",
    "            r = l1.val // 10\n",
    "            l1.val = l1.val % 10\n",
    "            pre = l1\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next if l2 else None\n",
    "        if r > 0:\n",
    "            node = ListNode(r)\n",
    "            pre.next = node\n",
    "        # return head\n",
    "        res, _ = self.reverse(head)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    def reverse(self, l):\n",
    "        pre, curr = None, l\n",
    "        n = 0\n",
    "        while curr:\n",
    "            n += 1\n",
    "            nxt = curr.next\n",
    "            curr.next = pre\n",
    "            pre, curr = curr, nxt\n",
    "        return pre, n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self,head:Optional[ListNode])->Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "    def addTwo(self,l1:Optional[ListNode],l2:Optional[ListNode])->Optional[ListNode]:\n",
    "        cur = dummy = ListNode()\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            cur.next = ListNode(carry%10)\n",
    "            carry //= 10\n",
    "            cur = cur.next\n",
    "            if l1:l1 = l1.next\n",
    "            if l2:l2 = l2.next\n",
    "        return dummy.next\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)\n",
    "        l3 = self.addTwo(l1,l2)\n",
    "        return self.reverseList(l3)\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "                \n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    " \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseln(self,head):\n",
    "        cur,pre = head,None\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1_n = self.reverseln(l1)\n",
    "        l2_n = self.reverseln(l2)\n",
    "\n",
    "        p1,p2 = l1_n,l2_n\n",
    "        dummy = ListNode()\n",
    "        p = dummy\n",
    "        carry = 0\n",
    "        while p1 or p2 or carry:\n",
    "            val = carry\n",
    "            if p1:\n",
    "                val += p1.val\n",
    "                p1 = p1.next\n",
    "            if p2:\n",
    "                val += p2.val\n",
    "                p2 = p2.next\n",
    "            \n",
    "            carry,val = divmod(val,10)\n",
    "\n",
    "            p.next = ListNode(val)\n",
    "            p = p.next\n",
    "        result_head = dummy.next\n",
    "        return self.reverseln(dummy.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def fun(l):\n",
    "            p = None\n",
    "            while l:\n",
    "                l.next, p, l = p, l, l.next\n",
    "            return p\n",
    "\n",
    "        def add(l1, l2):\n",
    "\n",
    "            if not l1: return l2\n",
    "            if not l2: return l1\n",
    "\n",
    "            l1.val += l2.val\n",
    "            if l1.val >= 10:\n",
    "                l1.next = add(ListNode(1), l1.next)\n",
    "                l1.val %= 10\n",
    "\n",
    "            l1.next = add(l1.next, l2.next)\n",
    "            return l1\n",
    "        \n",
    "        l1, l2 = fun(l1), fun(l2) \n",
    "\n",
    "        return fun(add(l1, l2))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def lreverse(head):\n",
    "            new = None\n",
    "            cur = head\n",
    "            while cur:\n",
    "                node = ListNode(cur.val)\n",
    "                node.next = new\n",
    "                new = node\n",
    "                cur = cur.next\n",
    "            return new\n",
    "        l1 = lreverse(l1)\n",
    "        l2 = lreverse(l2)\n",
    "        ans = None\n",
    "        flag = 0\n",
    "        while l1.val >= 0 or l2.val >= 0 or flag == 1:\n",
    "            t1 = l1.val if l1.val > 0 else 0\n",
    "            t2 = l2.val if l2.val > 0 else 0\n",
    "            if t1 + t2 + flag > 9:\n",
    "                node = ListNode(t1 + t2 + flag - 10)\n",
    "                flag = 1\n",
    "            else:\n",
    "                node = ListNode(t1 + t2 + flag)\n",
    "                flag = 0\n",
    "            node.next = ans\n",
    "            l1 = l1.next if l1.next else ListNode(-1)\n",
    "            l2 = l2.next if l2.next else ListNode(-1)\n",
    "            ans = node\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1 = self.pushStack(l1)\n",
    "        stack2 = self.pushStack(l2)\n",
    "\n",
    "        dummyHead = ListNode()\n",
    "        head = dummyHead\n",
    "        carry = 0\n",
    "        while stack1 or stack2 or carry:\n",
    "            val = carry\n",
    "            if stack1:\n",
    "                val += stack1.pop()\n",
    "            if stack2:\n",
    "                val += stack2.pop()\n",
    "            carry = val // 10\n",
    "            tmp = head.next\n",
    "            head.next = ListNode(val % 10)\n",
    "            head.next.next = tmp\n",
    "\n",
    "        return dummyHead.next\n",
    "\n",
    "    def pushStack(self, l: ListNode) -> List[int]:\n",
    "        stack = []\n",
    "        while l:\n",
    "            stack.append(l.val)\n",
    "            l = l.next\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [],[]\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry = 0\n",
    "        ans = None\n",
    "        while s1 or s2 or carry:\n",
    "            s = (s1.pop() if s1 else 0) + (s2.pop() if s2 else 0) + carry\n",
    "            carry, value = divmod(s, 10)\n",
    "            cur = ListNode(val = value)\n",
    "            cur.next = ans\n",
    "            ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry = 0\n",
    "        pre = None\n",
    "        while stack1 or stack2 or carry > 0:\n",
    "            sum = 0\n",
    "            sum += 0 if not stack1 else stack1.pop()\n",
    "            sum += 0 if not stack2 else stack2.pop()\n",
    "            sum += carry\n",
    "            carry = sum // 10\n",
    "            cur = ListNode(sum % 10)\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 第1步：将2个链表变成2个字符串\n",
    "        str1, str2 = '', ''\n",
    "        p1, p2 = l1, l2\n",
    "        while p1:\n",
    "            str1 += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            str2 += str(p2.val)\n",
    "            p2 = p2.next\n",
    "        \n",
    "        # 第2步：将2个字符串变成数字，相加\n",
    "        str3 = str(eval(''.join([str1, '+', str2])))\n",
    "        # str3 = str(int(str1) + int(str2))\n",
    "        \n",
    "        # 第3步：将结果变成链表\n",
    "        pre = None\n",
    "        for i in range(len(str3) - 1, -1, -1):\n",
    "            curnode = ListNode(int(str3[i]))\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1, stack2 = [], []\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        newListNode = None\n",
    "        carry = 0\n",
    "        while stack1 or stack2 or carry != 0:\n",
    "            a = 0 if not stack1 else stack1.pop()\n",
    "            b = 0 if not stack2 else stack2.pop()\n",
    "            sum = a + b + carry\n",
    "            carry = sum // 10\n",
    "            sum %= 10\n",
    "            curNode = ListNode(sum, newListNode)\n",
    "            newListNode = curNode\n",
    "        return newListNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        '''翻转链表 -> 计算结果 -> 翻转链表\n",
    "        '''\n",
    "\n",
    "        def reverse_list(head):\n",
    "            '''翻转链表\n",
    "            '''\n",
    "            if head is None or head.next is None:\n",
    "                # 无节点或只有一个节点，直接返回\n",
    "                return head\n",
    "\n",
    "            slow = head; fast = head.next\n",
    "            while(fast is not None):\n",
    "                tmp = fast.next\n",
    "                fast.next = slow\n",
    "                if slow is head:\n",
    "                    slow.next = None\n",
    "                slow = fast\n",
    "                fast = tmp\n",
    "            \n",
    "            return slow\n",
    "\n",
    "        l1 = reverse_list(l1)\n",
    "        l2 = reverse_list(l2)\n",
    "\n",
    "        dummy_head = ListNode()\n",
    "        curr_out = dummy_head\n",
    "        curr1 = l1\n",
    "        curr2 = l2\n",
    "        tmp = 0\n",
    "        while(curr1 is not None or curr2 is not None):\n",
    "            val = 0\n",
    "            if curr1 is not None:\n",
    "                val += curr1.val\n",
    "                curr1 = curr1.next\n",
    "\n",
    "            if curr2 is not None:\n",
    "                val += curr2.val\n",
    "                curr2 = curr2.next\n",
    "\n",
    "            val += tmp\n",
    "            curr_out.next = ListNode(val % 10)\n",
    "            curr_out = curr_out.next\n",
    "            tmp = val // 10\n",
    "\n",
    "        if tmp:\n",
    "            curr_out.next = ListNode(tmp)\n",
    "\n",
    "        rst = dummy_head.next\n",
    "        rst = reverse_list(rst)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        rl1, rl2 = self.reverse(l1), self.reverse(l2)\n",
    "        temp = 0\n",
    "        pre = cur = ListNode()\n",
    "        while rl1 or rl2 or temp:\n",
    "            temp += (rl1.val if rl1 else 0) + (rl2.val if rl2 else 0)\n",
    "            cur.next = ListNode(temp%10)\n",
    "            temp //= 10\n",
    "            cur = cur.next\n",
    "            if rl1: rl1 = rl1.next\n",
    "            if rl2: rl2 = rl2.next\n",
    "\n",
    "        return self.reverse(pre.next)\n",
    "    def reverse(self, head):\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            temp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = temp\n",
    "        \n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)\n",
    "        p0 = new = ListNode(None)\n",
    "        t = 0\n",
    "        while l1 and l2:\n",
    "            a = t + l1.val + l2.val\n",
    "            t, a = divmod(a, 10)\n",
    "            new.next = ListNode(a)\n",
    "            new = new.next\n",
    "            l2 = l2.next\n",
    "            l1 = l1.next\n",
    "        while l1:\n",
    "            a = t + l1.val\n",
    "            t, a = divmod(a, 10)\n",
    "            new.next = ListNode(a)\n",
    "            new = new.next\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            a = t + l2.val\n",
    "            t, a = divmod(a, 10)\n",
    "            new.next = ListNode(a)\n",
    "            new = new.next\n",
    "            l2 = l2.next\n",
    "        if t!=0:\n",
    "            new.next = ListNode(t)\n",
    "        return self.reverseList(p0.next)\n",
    "\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        dummy = ListNode()\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry = 0\n",
    "\n",
    "        while s1 or s2 or carry:\n",
    "            result_1 = 0 if not s1 else s1.pop()\n",
    "            result_2 = 0 if not s2 else s2.pop() \n",
    "            carry,val = divmod(result_1+result_2+carry, 10)\n",
    "            #carry = (result_1 + result_2 + carry) // 10\n",
    "            #val = (result_1 + result_2 + carry) % 10\n",
    "            dummy.next = ListNode(val, dummy.next)\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        num1,num2=0,0\n",
    "        while l1!=None:\n",
    "            num1=num1*10+l1.val\n",
    "            l1=l1.next\n",
    "        while l2!=None:\n",
    "            num2=num2*10+l2.val\n",
    "            l2=l2.next\n",
    "        ret=ListNode()\n",
    "        ret_num=str(num1+num2)\n",
    "        last=ret\n",
    "        for i in ret_num:\n",
    "            q=ListNode(val=int(i))\n",
    "            last.next=q\n",
    "            last=q\n",
    "        return ret.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        nex = None\n",
    "        s = 0\n",
    "        while stack1 or stack2 or s:\n",
    "            n1 = stack1.pop() if stack1 else 0\n",
    "            n2 = stack2.pop() if stack2 else 0\n",
    "            curvalue = n1 + n2 + s\n",
    "            s = curvalue // 10\n",
    "            curvalue %= 10\n",
    "            node = ListNode(val=curvalue, next=nex)\n",
    "            nex = node\n",
    "        return nex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p1 = ListNode(0)\n",
    "        p2 = ListNode(0)\n",
    "        while (l1):\n",
    "            tmp = l1.next\n",
    "            l1.next = p1.next\n",
    "            p1.next = l1\n",
    "            l1 = tmp\n",
    "        while(l2):\n",
    "            tmp = l2.next\n",
    "            l2.next = p2.next\n",
    "            p2.next = l2\n",
    "            l2 = tmp\n",
    "        sum1 = ListNode(0)\n",
    "        cur = sum1\n",
    "        cur1 = p1.next\n",
    "        cur2 = p2.next\n",
    "        flag = 0\n",
    "        while(cur1 and cur2):\n",
    "            sum_ = cur1.val + cur2.val + flag\n",
    "            remainder = sum_ % 10\n",
    "            flag = sum_ // 10\n",
    "            cur.next = ListNode(remainder)\n",
    "            cur = cur.next\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next\n",
    "        while(cur1):\n",
    "            sum_ = cur1.val + flag\n",
    "            remainder = sum_ % 10\n",
    "            flag = sum_ // 10\n",
    "            cur.next = ListNode(remainder)\n",
    "            cur = cur.next\n",
    "            cur1 = cur1.next\n",
    "        while(cur2):\n",
    "            sum_ = cur2.val + flag\n",
    "            remainder = sum_ % 10\n",
    "            flag = sum_ // 10\n",
    "            cur.next = ListNode(remainder)\n",
    "            cur = cur.next\n",
    "            cur2 = cur2.next\n",
    "        if flag != 0:\n",
    "            cur.next = ListNode(flag)\n",
    "        cur = sum1.next\n",
    "        sum1.next = None\n",
    "        while(cur):\n",
    "            tmp = cur.next\n",
    "            cur.next = sum1.next\n",
    "            sum1.next = cur\n",
    "            cur = tmp\n",
    "        return sum1.next\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        return self.reverseList(self.addTwo(self.reverseList(l1),self.reverseList(l2)))\n",
    "    def reverseList(self,head):\n",
    "        cur=head\n",
    "        prev=None\n",
    "        while cur:\n",
    "            temp=cur.next\n",
    "            cur.next=prev\n",
    "            prev=cur\n",
    "            cur=temp\n",
    "        return prev\n",
    "    def addTwo(self,l1,l2):\n",
    "        num_0=0\n",
    "        num_10=0\n",
    "        cur=dum=ListNode()\n",
    "        while l1 or l2:\n",
    "            if not l1:\n",
    "                l1=ListNode(0)\n",
    "            if not l2:\n",
    "                l2=ListNode(0)\n",
    "            num_0=(l1.val+l2.val+num_10)%10\n",
    "            num_10=(l1.val+l2.val+num_10)//10\n",
    "            cur.next=ListNode(val=num_0)\n",
    "            cur=cur.next\n",
    "            l1=l1.next\n",
    "            l2=l2.next\n",
    "        if num_10!=0:\n",
    "            cur.next=ListNode(val=1)\n",
    "        return dum.next\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p1, p2 = l1, l2\n",
    "        s1, s2 = '', ''\n",
    "        while p1:\n",
    "            s1 += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            s2 += str(p2.val)\n",
    "            p2 = p2.next\n",
    "        s3 = str(int(s1) + int(s2))\n",
    "        pre = None\n",
    "        for i in range(len(s3) - 1, -1, -1):\n",
    "            curnode = ListNode(int(s3[i]))\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1=self.reverse(l1)\n",
    "        l2=self.reverse(l2)\n",
    "        l3=self.addTwo(l1,l2)\n",
    "        return self.reverse(l3)\n",
    "    def reverse(self,head:Optional[ListNode])->Optional[ListNode]:\n",
    "        pre=None\n",
    "        cur=head\n",
    "        while cur:\n",
    "          n=cur.next\n",
    "          cur.next=pre\n",
    "          pre=cur\n",
    "          cur=n\n",
    "        return pre\n",
    "    def addTwo(self,l1:Optional[ListNode],l2:Optional[ListNode])->Optional:\n",
    "        dummy=ListNode(0)\n",
    "        cur=dummy\n",
    "        carry=0\n",
    "        while l1 or l2 or carry:\n",
    "            carry+=(l1.val if l1 else 0)+(l2.val if l2 else 0)\n",
    "            cur.next=ListNode(carry%10)\n",
    "            cur=cur.next\n",
    "            carry//=10\n",
    "            if l1:l1=l1.next \n",
    "            if l2:l2=l2.next \n",
    "        return dummy.next\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if l1.val == 0:\n",
    "            return l2\n",
    "        if l2.val == 0:\n",
    "            return l1\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        head = ListNode()\n",
    "        remainder = 0\n",
    "        res = 0\n",
    "        while stack1 and stack2:\n",
    "            num1 = stack1.pop()\n",
    "            num2 = stack2.pop()\n",
    "            res = (num1 + num2 + remainder) % 10\n",
    "            remainder = (num1 + num2 + remainder) // 10\n",
    "            node = ListNode(res)\n",
    "            node.next = head.next\n",
    "            head.next = node\n",
    "        \n",
    "        if len(stack1) != 0:\n",
    "            while stack1:\n",
    "                num = stack1.pop()\n",
    "                res = (num + remainder) % 10\n",
    "                remainder = (num + remainder) // 10\n",
    "                node = ListNode(res)\n",
    "                node.next = head.next\n",
    "                head.next = node\n",
    "        \n",
    "        if len(stack2) != 0:\n",
    "            while stack2:\n",
    "                num = stack2.pop()\n",
    "                res = (num + remainder) % 10\n",
    "                remainder = (num + remainder) // 10\n",
    "                node = ListNode(res)\n",
    "                node.next = head.next\n",
    "                head.next = node\n",
    "        \n",
    "        if len(stack1) == 0 and len(stack2) == 0:\n",
    "            if remainder == 0:\n",
    "                return head.next\n",
    "            else:\n",
    "                node = ListNode(remainder)\n",
    "                node.next = head.next\n",
    "                head.next = node\n",
    "                return head.next\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverse(head=l1)\n",
    "        l2 = self.reverse(head=l2)\n",
    "        cur = dummy = ListNode()\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:\n",
    "            if l1: carry += l1.val\n",
    "            if l2: carry += l2.val\n",
    "\n",
    "            cur.next = ListNode(carry%10)\n",
    "            carry //= 10\n",
    "            cur = cur.next\n",
    "\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        return self.reverse(dummy.next)\n",
    "            \n",
    "                \n",
    "\n",
    "\n",
    "    def reverse(self,head):\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stk1, stk2 = [], []\n",
    "        while l1:\n",
    "            stk1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stk2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        c = 0\n",
    "        a, b = 0, 0\n",
    "        head, f = None, None\n",
    "        while stk1 or stk2:\n",
    "            if stk1:\n",
    "                a = stk1.pop(-1)\n",
    "            if stk2:\n",
    "                b = stk2.pop(-1)\n",
    "            # ans *= 10\n",
    "            f = head\n",
    "            t = ListNode((a+b+c) % 10, f)\n",
    "            head = t\n",
    "            c = (a + b + c) // 10\n",
    "            a = b = 0\n",
    "        if not stk1 and not stk2 and c != 0:\n",
    "            f = head\n",
    "            t = ListNode((a+b+c) % 10, f)\n",
    "            head = t\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        str1, str2 = '', ''\n",
    "        p1, p2 = l1, l2\n",
    "        while p1:\n",
    "            str1 += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            str2 += str(p2.val)\n",
    "            p2 = p2.next\n",
    "        str3 = str(eval(''.join([str1, '+', str2])))\n",
    "        pre = None\n",
    "        for i in range(len(str3) - 1, -1, -1):\n",
    "            curnode = ListNode(int(str3[i]))\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def addtwo(l1,l2,carry=0):\n",
    "            if not l1 and not l2:\n",
    "                return ListNode(carry) if carry else None\n",
    "            if not l1:\n",
    "                l1,l2 = l2,l1\n",
    "            carry += l1.val + (l2.val if l2 else 0)\n",
    "            l1.val = carry % 10\n",
    "            l1.next = addtwo(l1.next,(l2.next if l2 else None),carry//10)\n",
    "            return l1\n",
    "        def reverse(node):\n",
    "            pre,cur = None,node\n",
    "            while cur:\n",
    "                node_next = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = node_next\n",
    "            return pre\n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        l3 = addtwo(l1,l2)\n",
    "        return reverse(l3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        num1 = []\n",
    "        num2 = []\n",
    "        while l1:\n",
    "            num1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            num2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        max_n = max(len(num1), len(num2))\n",
    "        if max_n != len(num1):\n",
    "            num1 = [0 for _ in range(max_n-len(num1))] + num1\n",
    "        if max_n != len(num2):\n",
    "            num2 = [0 for _ in range(max_n-len(num2))] + num2\n",
    "\n",
    "        # core\n",
    "        res = []\n",
    "        jin = 0\n",
    "        for i in range(max_n-1, -1, -1):\n",
    "            value = num1[i] + num2[i] + jin\n",
    "            jin = value // 10\n",
    "            cur = value % 10\n",
    "            res.append(cur)\n",
    "        if jin > 0:\n",
    "            res.append(jin)\n",
    "        res = res[::-1]\n",
    "\n",
    "        dump = ListNode()\n",
    "        head = dump\n",
    "        for i in range(len(res)):\n",
    "            tmp = ListNode()\n",
    "            tmp.val = res[i]\n",
    "            head.next = tmp\n",
    "            head = head.next \n",
    "        return dump.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(l):\n",
    "            pre = None\n",
    "            cur = l\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = tmp\n",
    "            return pre\n",
    "        L1, L2 = [], []\n",
    "        while l1:\n",
    "            L1.append(l1)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            L2.append(l2)\n",
    "            l2 = l2.next\n",
    "\n",
    "        up = 0\n",
    "        head = ListNode()\n",
    "        cur = head\n",
    "        while L1 or L2 or up:\n",
    "            val = up\n",
    "            if L1:\n",
    "                val += L1.pop().val\n",
    "            if L2:\n",
    "                val += L2.pop().val\n",
    "            if val>=10:\n",
    "                val-=10\n",
    "                up = 1\n",
    "            else:\n",
    "                up = 0\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "        return reverse(head.next)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        num1 = num2 = 0\n",
    "        while l1:\n",
    "            num1 = 10 * num1 + l1.val\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            num2 = 10 * num2 + l2.val\n",
    "            l2 = l2.next\n",
    "        h = ListNode()\n",
    "        cur = h\n",
    "        for c in str(num1 + num2):\n",
    "            cur.next = ListNode(int(c), None)\n",
    "            cur = cur.next\n",
    "        return h.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1_list = []\n",
    "        l2_list = []\n",
    "\n",
    "        while l1:\n",
    "            l1_list.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        while l2:\n",
    "            l2_list.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        carry = 0\n",
    "        ans = None\n",
    "\n",
    "        while l1_list or l2_list:\n",
    "            if l1_list:\n",
    "                tmp1 = l1_list.pop()\n",
    "            else:\n",
    "                tmp1 = 0\n",
    "            \n",
    "            if l2_list:\n",
    "                tmp2 = l2_list.pop()\n",
    "            else:\n",
    "                tmp2 = 0\n",
    "\n",
    "            value = (tmp1 + tmp2 + carry) % 10\n",
    "            carry = (tmp1 + tmp2 + carry) // 10\n",
    "\n",
    "            if not ans:\n",
    "                ans = ListNode(value)\n",
    "            else:\n",
    "                head = ListNode(value)\n",
    "                head.next = ans\n",
    "                ans = head\n",
    "        \n",
    "        if carry:\n",
    "            head = ListNode(carry)\n",
    "            head.next = ans\n",
    "            ans = head\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        '''\n",
    "        # 方法一：反转列表\n",
    "        def reverse(l):\n",
    "            pre = None\n",
    "            cur = l\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = tmp\n",
    "            return pre\n",
    "        \n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        add = 0\n",
    "        while l1 or l2 or add:\n",
    "            if l1:\n",
    "                val1 = l1.val\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                val1 = 0\n",
    "            if l2:\n",
    "                val2 = l2.val\n",
    "                l2 = l2.next\n",
    "            else:\n",
    "                val2 = 0\n",
    "            val = val1 + val2 + add\n",
    "            new_node = ListNode(val%10)\n",
    "            add = val // 10\n",
    "            cur.next = new_node\n",
    "            cur = cur.next\n",
    "        return reverse(dummy.next)\n",
    "        '''\n",
    "\n",
    "        # 方法二：栈\n",
    "        stack1 = []\n",
    "        head1 = l1\n",
    "        while head1:\n",
    "            stack1.append(head1.val)\n",
    "            head1 = head1.next\n",
    "        stack2 = []\n",
    "        head2 = l2\n",
    "        while head2:\n",
    "            stack2.append(head2.val)\n",
    "            head2 = head2.next\n",
    "        \n",
    "        add = 0\n",
    "        back = None\n",
    "        while stack1 or stack2 or add:\n",
    "            if stack1:\n",
    "                val1 = stack1.pop()\n",
    "            else:\n",
    "                val1 = 0\n",
    "            if stack2:\n",
    "                val2 = stack2.pop()\n",
    "            else:\n",
    "                val2 = 0\n",
    "            val = val1 + val2 + add\n",
    "            new_node = ListNode(val%10)\n",
    "            add = val // 10\n",
    "            new_node.next = back\n",
    "            back = new_node\n",
    "        return back"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1, stack2 = [], []\n",
    "        \n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        carry = 0\n",
    "\n",
    "        res_lst = []\n",
    "        while stack1 or stack2 or carry > 0:\n",
    "            if stack1 and stack2:\n",
    "                temp_val = (stack1.pop() + stack2.pop() + carry) \n",
    "            elif stack1:\n",
    "                temp_val = (stack1.pop() + carry) \n",
    "            elif stack2:\n",
    "                temp_val = (stack2.pop() + carry)\n",
    "            else:\n",
    "                temp_val = carry\n",
    "            \n",
    "            real_val = temp_val % 10\n",
    "            carry = temp_val // 10\n",
    "            res_lst.append(real_val)\n",
    "        \n",
    "        res_lst = res_lst[::-1]\n",
    "        res_node = ListNode(res_lst[0])\n",
    "        temp = res_node\n",
    "        if len(res_lst) == 1:\n",
    "            return res_node\n",
    "        \n",
    "        for val in res_lst[1:]:\n",
    "            temp.next = ListNode(val)\n",
    "            temp = temp.next\n",
    "        \n",
    "        return res_node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 先反转链表，再用0002.两数相加方法解决\n",
    "        # 反转l1，l2\n",
    "        rl1 = self.reverse(l1)\n",
    "        rl2 = self.reverse(l2)\n",
    "\n",
    "        dummy_head = ListNode(-1)\n",
    "        cur = dummy_head\n",
    "        carry = 0\n",
    "        while rl1 or rl2 or carry:\n",
    "            if rl1:\n",
    "                num1 = rl1.val\n",
    "                rl1 = rl1.next\n",
    "            else:\n",
    "                num1 = 0\n",
    "            if rl2:\n",
    "                num2 = rl2.val\n",
    "                rl2 = rl2.next\n",
    "            else:\n",
    "                num2 = 0\n",
    "            sum = num1 + num2 + carry\n",
    "            carry = sum // 10\n",
    "            inplace_sum = sum % 10\n",
    "            cur.next = ListNode(inplace_sum)\n",
    "            cur = cur.next\n",
    "\n",
    "        # 将结果反转\n",
    "        ans = self.reverse(dummy_head.next)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    # 反转链表函数\n",
    "    def reverse(self, l):\n",
    "        pre = None\n",
    "        cur = l\n",
    "        while cur:\n",
    "            temp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = temp\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur//10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1, stack2 = [],[]\n",
    "        # 遍历两个链表，进行入栈操作\n",
    "        while l1 or l2:\n",
    "            if l1:\n",
    "                stack1.append(l1.val)\n",
    "                l1 = l1.next\n",
    "            \n",
    "            if l2:\n",
    "                stack2.append(l2.val)\n",
    "                l2 = l2.next\n",
    "        \n",
    "        # 出栈操作，并按位相加\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while stack1 and stack2:\n",
    "            n1 = stack1.pop()\n",
    "            n2 = stack2.pop()\n",
    "\n",
    "            r = n1 + n2 + carry\n",
    "\n",
    "            carry = r // 10\n",
    "            val = r % 10\n",
    "            cur_node = ListNode(val)\n",
    "            cur_node.next = ans\n",
    "            ans = cur_node\n",
    "        \n",
    "        while stack1:\n",
    "            n1 = stack1.pop()\n",
    "\n",
    "            r = n1 + carry\n",
    "            carry = r // 10\n",
    "            val = r % 10\n",
    "            cur_node = ListNode(val)\n",
    "            cur_node.next = ans\n",
    "            ans = cur_node\n",
    "        \n",
    "        while stack2:\n",
    "            n1 = stack2.pop()\n",
    "\n",
    "            r = n1 + carry\n",
    "            carry = r // 10\n",
    "            val = r % 10\n",
    "            cur_node = ListNode(val)\n",
    "            cur_node.next = ans\n",
    "            ans = cur_node\n",
    "        \n",
    "        if carry > 0:\n",
    "            cur_node = ListNode(carry)\n",
    "            cur_node.next = ans\n",
    "            ans = cur_node\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0,    next=None):\n",
    "    \n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1=''\n",
    "        while l1:\n",
    "            s1=s1+str(l1.val)\n",
    "            l1=l1.next\n",
    "        s2 = ''\n",
    "        while l2:\n",
    "            s2 = s2 + str(l2.val)\n",
    "            l2 = l2.next\n",
    "        l=[int(i) for i in list(str(int(s1)+int(s2)))]\n",
    "        hh=ListNode(l.pop(0),None)\n",
    "        h=hh\n",
    "        while l:\n",
    "            nd=ListNode(l.pop(0),None)\n",
    "            h.next=nd\n",
    "            h=h.next\n",
    "        return hh"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1_sum = \"\"\n",
    "        l2_sum = \"\"\n",
    "        p1 = l1\n",
    "        p2 = l2\n",
    "        while p1 is not None:\n",
    "            l1_sum += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2 is not None:\n",
    "            l2_sum += str(p2.val)\n",
    "            p2 = p2.next\n",
    "\n",
    "        num1 = int(l1_sum)\n",
    "        num2 = int(l2_sum)\n",
    "        nums_sum_str = str(num1 + num2)\n",
    "        dummy = ListNode()\n",
    "        tail = dummy\n",
    "        for char in nums_sum_str:\n",
    "            node = ListNode(int(char))\n",
    "            tail.next = node\n",
    "            tail = tail.next\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1 or l2:\n",
    "            if l1:\n",
    "                stack1.append(l1.val)\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                stack2.append(l2.val)\n",
    "                l2 = l2.next\n",
    "        cur = None\n",
    "        carry = 0\n",
    "        while stack1 or stack2 or carry:\n",
    "            val1 = stack1.pop() if stack1 else 0\n",
    "            val2 = stack2.pop() if stack2 else 0\n",
    "            total = val1 + val2 + carry\n",
    "            carry = total // 10\n",
    "            temp = ListNode(total % 10)\n",
    "            if cur:\n",
    "                temp.next = cur\n",
    "                cur = temp\n",
    "            else:\n",
    "                cur = temp\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack_1 = []\n",
    "        stack_2 = []\n",
    "        while l1:\n",
    "            stack_1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        while l2:\n",
    "            stack_2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        following = None\n",
    "        carry = 0\n",
    "        while stack_1 or stack_2:\n",
    "            num_1 = stack_1.pop() if stack_1 else 0\n",
    "            num_2 = stack_2.pop() if stack_2 else 0\n",
    "            temp = (carry + num_1 + num_2) % 10\n",
    "            carry = (carry + num_1 + num_2) // 10\n",
    "            curr = ListNode(temp)\n",
    "            curr.next = following\n",
    "            following = curr\n",
    "        \n",
    "        if carry:\n",
    "            curr = ListNode(carry)\n",
    "            curr.next = following\n",
    "            following = curr\n",
    "\n",
    "        return following"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        def reverse(root):\n",
    "            if not root:\n",
    "                return root\n",
    "            pre = None\n",
    "            cur = root\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre, cur = cur, nxt\n",
    "            return pre\n",
    "\n",
    "        def _add(l1, l2, carry):\n",
    "            \n",
    "            if l1 is None and l2 is None:\n",
    "                return ListNode(carry) if carry else None\n",
    "            if l1 is None:\n",
    "                l1, l2 = l2, l1\n",
    "\n",
    "            carry += l1.val + (l2.val if l2 else 0)\n",
    "            l1.val = carry % 10\n",
    "            l1.next = _add(l1.next, l2.next if l2 else None, carry // 10)\n",
    "            return l1\n",
    "\n",
    "        rev_l1 = reverse(l1)\n",
    "        rev_l2 = reverse(l2)\n",
    "\n",
    "        rev_root = _add(rev_l1, rev_l2, 0)               \n",
    "        return reverse(rev_root)\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverList(self,head):\n",
    "        pre=None\n",
    "        cur=head\n",
    "        while cur:\n",
    "            temp=cur.next\n",
    "            cur.next=pre\n",
    "            pre=cur\n",
    "            cur=temp\n",
    "        return pre\n",
    "    \n",
    "    def addtwoSum(self,l1,l2):\n",
    "        cur=dummy=ListNode()\n",
    "        carry=0\n",
    "        while l1 or l2 or carry:\n",
    "            if l1: carry=carry+l1.val\n",
    "            if l2: carry=carry+l2.val\n",
    "            cur.next=ListNode(carry%10)\n",
    "            carry=carry//10\n",
    "            cur=cur.next\n",
    "            if l1: l1=l1.next\n",
    "            if l2: l2=l2.next\n",
    "\n",
    "        return dummy.next\n",
    "    \n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        reverl1=self.reverList(l1)\n",
    "        reverl2=self.reverList(l2)\n",
    "        addresult=self.addtwoSum(reverl1,reverl2)\n",
    "        result=self.reverList(addresult)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "\r\n",
    "\r\n",
    "def rev(head):\r\n",
    "    cur, pre = head, None\r\n",
    "    while cur:\r\n",
    "        nxt = cur.next\r\n",
    "        cur.next = pre\r\n",
    "        pre = cur\r\n",
    "        cur = nxt\r\n",
    "    return pre\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\r\n",
    "        l1 = rev(l1)\r\n",
    "        l2 = rev(l2)\r\n",
    "\r\n",
    "        cur = dummy = ListNode()\r\n",
    "        carry = 0\r\n",
    "        while l1 or l2 or carry:\r\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\r\n",
    "            cur.next = ListNode(val=carry % 10)\r\n",
    "            carry //= 10\r\n",
    "            cur = cur.next\r\n",
    "            if l1:\r\n",
    "                l1 = l1.next\r\n",
    "            if l2:\r\n",
    "                l2 = l2.next\r\n",
    "        return rev(dummy.next)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        #Optional 可选参数\n",
    "        def decodeNode(ln: ListNode) -> str:\n",
    "            snum = \"\"\n",
    "            i = ln\n",
    "            while(i != None):\n",
    "                snum += str(i.val)\n",
    "                i = i.next\n",
    "            return snum\n",
    "\n",
    "        def encodeNode(n: int) -> ListNode:\n",
    "            sn = str(n)[::-1]\n",
    "            # print(sn)\n",
    "            lnnext = ListNode(val=int(sn[0]))\n",
    "            for i in range(1,len(sn)):\n",
    "                lnnum = ListNode(int(sn[i]),lnnext)\n",
    "                lnnext = lnnum\n",
    "            return lnnext\n",
    "\n",
    "            \n",
    "        s1 = decodeNode(l1)\n",
    "        s2 = decodeNode(l2)\n",
    "        \n",
    "        ia = int(s1) + int(s2)\n",
    "        # print(s1,s2,ia)\n",
    "        return encodeNode(ia)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(l):\n",
    "            pre = None\n",
    "            cur = l\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = tmp\n",
    "            return pre\n",
    "        L1, L2 = [], []\n",
    "        while l1:\n",
    "            L1.append(l1)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            L2.append(l2)\n",
    "            l2 = l2.next\n",
    "\n",
    "        up = 0\n",
    "        res = []\n",
    "        while L1 or L2 or up:\n",
    "            val = up\n",
    "            if L1:\n",
    "                val += L1.pop().val\n",
    "            if L2:\n",
    "                val += L2.pop().val\n",
    "            if val>=10:\n",
    "                val-=10\n",
    "                up = 1\n",
    "            else:\n",
    "                up = 0\n",
    "            res.append(ListNode(val))\n",
    "\n",
    "        for i in range(len(res)-1, -1, -1):\n",
    "            if i == 0:\n",
    "                res[i].next = None\n",
    "            else:\n",
    "                res[i].next = res[i-1]            \n",
    "        return res[-1]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 反转链表\n",
    "        pre=None\n",
    "        cur=head # 将当前指针指向首元结点\n",
    "        while cur:\n",
    "            nxt=cur.next\n",
    "            cur.next=pre\n",
    "            pre=cur\n",
    "            cur=nxt\n",
    "        return pre\n",
    "        \n",
    "    def resultList(self, l1: Optional[ListNode] , l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 将两个链表进行相加运算\n",
    "        p=ass=ListNode(None)\n",
    "        carry=0\n",
    "        while l1 or l2:\n",
    "            temp=(l1.val if l1 else 0)+(l2.val if l2 else 0)+carry\n",
    "            p.next=ListNode(temp%10)\n",
    "            p=p.next\n",
    "            carry=temp//10 # 取整\n",
    "            l1=l1.next if l1 else 0\n",
    "            l2=l2.next if l2 else 0\n",
    "        if carry:\n",
    "            p.next=ListNode(1)\n",
    "        return ass.next\n",
    "    \n",
    "    def addTwoNumbers(self, l1: Optional[ListNode] , l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1=self.reverseList(l1) # 将两个链表进行反转操作\n",
    "        l2=self.reverseList(l2)\n",
    "        l3=self.resultList(l1,l2)\n",
    "        return self.reverseList(l3)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def _reverser(self, cur: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 双指针迭代-反转\n",
    "        # pred=sentienlle=ListNode()\n",
    "        pred = None\n",
    "        while cur:\n",
    "            temp=cur.next\n",
    "            cur.next=pred\n",
    "            pred=cur\n",
    "            cur=temp\n",
    "        return pred\n",
    "\n",
    "    def _addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:\n",
    "        # 递归-两数相加\n",
    "        if l1 is None and l2 is None:\n",
    "            return ListNode(carry) if carry else None\n",
    "        # 设置假定l1是最长的那个\n",
    "        if l1 is None:\n",
    "            l1,l2=l2,l1\n",
    "        carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "        l1.val = carry%10\n",
    "        l1.next = self._addTwo(l1.next, l2.next if l2 else None,carry=carry//10)\n",
    "        return l1\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self._reverser(l1)\n",
    "        l2 = self._reverser(l2)\n",
    "        l1 = self._addTwo(l1, l2)\n",
    "        return self._reverser(l1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # reverse the linked list\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)\n",
    "        l3 = self.addTwo(l1, l2)\n",
    "        return self.reverseList(l3)\n",
    "\n",
    "\n",
    "    def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        carry = 0\n",
    "        dummyHead = ListNode(0)\n",
    "        cur = dummyHead\n",
    "        while l1 or l2:\n",
    "            x = 0 if l1 == None else l1.val\n",
    "            y = 0 if l2 == None else l2.val\n",
    "            sum = 0\n",
    "            sum += (x + y + carry)\n",
    "\n",
    "            carry = sum // 10\n",
    "            sum = sum % 10\n",
    "\n",
    "            cur.next = ListNode(sum)\n",
    "            cur = cur.next\n",
    "\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        if carry != 0:\n",
    "            cur.next = ListNode(carry)\n",
    "        return dummyHead.next\n",
    "\n",
    "\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def fanzhuan(l: Optional[ListNode])-> Optional[ListNode]:\n",
    "        cur = l\n",
    "        pre = None\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p1 = fanzhuan(l1)\n",
    "        p2 = fanzhuan(l2)\n",
    "        p3 = dummy = ListNode()\n",
    "        carry = 0\n",
    "        while p1 or p2 or carry:\n",
    "            if p1: carry += p1.val\n",
    "            if p2: carry += p2.val\n",
    "            p3.next = ListNode(carry % 10)  # 每个节点保存一个数位\n",
    "            carry //= 10  # 新的进位\n",
    "            p3 = p3.next  # 下一个节点\n",
    "            if p1: p1 = p1.next  # 下一个节点\n",
    "            if p2: p2 = p2.next  # 下一个节点\n",
    "\n",
    "        return fanzhuan(dummy.next)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        #反转链表\n",
    "        pre1=None\n",
    "        cur1=l1\n",
    "        while cur1:\n",
    "            nxt1 = cur1.next\n",
    "            cur1.next = pre1\n",
    "            pre1 = cur1\n",
    "            cur1 = nxt1\n",
    "        #此时l1头节点pre1\n",
    "        pre2=None\n",
    "        cur2=l2\n",
    "        while cur2:\n",
    "            nxt2 = cur2.next\n",
    "            cur2.next = pre2\n",
    "            pre2 = cur2\n",
    "            cur2 = nxt2\n",
    "        #此时l2头节点pre2:\n",
    "        cur1 = pre1\n",
    "        cur2 = pre2\n",
    "        dummy = cur1\n",
    "        flag = 0\n",
    "        while cur1 and cur2:\n",
    "            cur1.val = cur1.val + cur2.val + flag\n",
    "            flag = 0\n",
    "            if cur1.val >9:\n",
    "                cur1.val -= 10\n",
    "                flag +=1\n",
    "            pre1 = cur1\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next\n",
    "\n",
    "        while cur1:\n",
    "            cur1.val = cur1.val + flag\n",
    "            flag = 0\n",
    "            if cur1.val >9:\n",
    "                cur1.val -= 10\n",
    "                flag +=1\n",
    "            pre1 = cur1\n",
    "            cur1 = cur1.next\n",
    "\n",
    "        while cur2:\n",
    "            cur1 = ListNode(val = 0)\n",
    "            pre1.next = cur1\n",
    "            cur1.val = cur2.val + flag\n",
    "            flag = 0\n",
    "            if cur1.val >9:\n",
    "                cur1.val -= 10\n",
    "                flag +=1\n",
    "            pre1 = cur1\n",
    "            cur2 = cur2.next\n",
    "            cur1 = cur1.next\n",
    "\n",
    "        if flag == 1:\n",
    "            cur1 = ListNode(val = 1)\n",
    "            pre1.next = cur1\n",
    "\n",
    "        pre1=None\n",
    "        cur1=dummy\n",
    "        while cur1:\n",
    "            nxt1 = cur1.next\n",
    "            cur1.next = pre1\n",
    "            pre1 = cur1\n",
    "            cur1 = nxt1\n",
    "        return pre1\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1 = []\n",
    "        s2 = []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1=l1.next\n",
    "        \n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        carry = 0\n",
    "        ans = None\n",
    "        while s1 or s2 or carry != 0:\n",
    "            if s1:\n",
    "                a = s1.pop()\n",
    "            else:\n",
    "                a = 0\n",
    "            if s2:\n",
    "                b = s2.pop()\n",
    "            else:\n",
    "                b = 0\n",
    "            num = a + b + carry\n",
    "            carry = num // 10\n",
    "            cur = num % 10\n",
    "            node = ListNode(cur)\n",
    "            node.next = ans\n",
    "            ans = node\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def _reverser(self, cur: Optional[ListNode], pred: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 递归-反转\n",
    "        if cur is None:\n",
    "            return pred\n",
    "        res = self._reverser(cur.next, cur)\n",
    "        cur.next = pred\n",
    "        return res\n",
    "\n",
    "    def _addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:\n",
    "        # 递归-两数相加\n",
    "        if l1 is None and l2 is None:\n",
    "            return ListNode(carry) if carry else None\n",
    "        # 设置假定l1是最长的那个\n",
    "        if l1 is None:\n",
    "            l1,l2=l2,l1\n",
    "        carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "        l1.val = carry%10\n",
    "        l1.next = self._addTwo(l1.next, l2.next if l2 else None,carry=carry//10)\n",
    "        return l1\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self._reverser(l1, None)\n",
    "        l2 = self._reverser(l2, None)\n",
    "        l1 = self._addTwo(l1, l2)\n",
    "        return self._reverser(l1, None)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "#梁佟辉方法：反转链表相加再反转链表\n",
    "# class Solution:\n",
    "#     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "#         #反转链表\n",
    "#         pre1=None\n",
    "#         cur1=l1\n",
    "#         while cur1:\n",
    "#             nxt1 = cur1.next\n",
    "#             cur1.next = pre1\n",
    "#             pre1 = cur1\n",
    "#             cur1 = nxt1\n",
    "#         #此时l1头节点pre1\n",
    "#         pre2=None\n",
    "#         cur2=l2\n",
    "#         while cur2:\n",
    "#             nxt2 = cur2.next\n",
    "#             cur2.next = pre2\n",
    "#             pre2 = cur2\n",
    "#             cur2 = nxt2\n",
    "#         #此时l2头节点pre2:\n",
    "#         cur1 = pre1\n",
    "#         cur2 = pre2\n",
    "#         dummy = cur1\n",
    "#         flag = 0\n",
    "#         while cur1 and cur2:\n",
    "#             cur1.val = cur1.val + cur2.val + flag\n",
    "#             flag = 0\n",
    "#             if cur1.val >9:\n",
    "#                 cur1.val -= 10\n",
    "#                 flag +=1\n",
    "#             pre1 = cur1\n",
    "#             cur1 = cur1.next\n",
    "#             cur2 = cur2.next\n",
    "\n",
    "#         while cur1:\n",
    "#             cur1.val = cur1.val + flag\n",
    "#             flag = 0\n",
    "#             if cur1.val >9:\n",
    "#                 cur1.val -= 10\n",
    "#                 flag +=1\n",
    "#             pre1 = cur1\n",
    "#             cur1 = cur1.next\n",
    "\n",
    "#         while cur2:\n",
    "#             cur1 = ListNode(val = 0)\n",
    "#             pre1.next = cur1\n",
    "#             cur1.val = cur2.val + flag\n",
    "#             flag = 0\n",
    "#             if cur1.val >9:\n",
    "#                 cur1.val -= 10\n",
    "#                 flag +=1\n",
    "#             pre1 = cur1\n",
    "#             cur2 = cur2.next\n",
    "#             cur1 = cur1.next\n",
    "\n",
    "#         if flag == 1:\n",
    "#             cur1 = ListNode(val = 1)\n",
    "#             pre1.next = cur1\n",
    "\n",
    "#         pre1=None\n",
    "#         cur1=dummy\n",
    "#         while cur1:\n",
    "#             nxt1 = cur1.next\n",
    "#             cur1.next = pre1\n",
    "#             pre1 = cur1\n",
    "#             cur1 = nxt1\n",
    "#         return pre1\n",
    "\n",
    "#0x3f:\n",
    "class Solution:\n",
    "    # 视频讲解 https://www.bilibili.com/video/BV1sd4y1x7KN/\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = dummy = ListNode()  # 哨兵节点\n",
    "        carry = 0  # 进位\n",
    "        while l1 or l2 or carry:  # 有一个不是空节点，或者还有进位，就继续迭代\n",
    "            if l1: carry += l1.val  # 节点值和进位加在一起\n",
    "            if l2: carry += l2.val  # 节点值和进位加在一起\n",
    "            cur.next = ListNode(carry % 10)  # 每个节点保存一个数位\n",
    "            carry //= 10  # 新的进位\n",
    "            cur = cur.next  # 下一个节点\n",
    "            if l1: l1 = l1.next  # 下一个节点\n",
    "            if l2: l2 = l2.next  # 下一个节点\n",
    "        return dummy.next  # 哨兵节点的下一个节点就是头节点\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)  # l1 和 l2 反转后，就变成【2. 两数相加】了\n",
    "        l3 = self.addTwo(l1, l2)\n",
    "        return self.reverseList(l3)  # 计算完毕后再反转\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            total = a + b + carry\n",
    "            carry = total // 10\n",
    "            cur = total % 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        st1=[]\n",
    "        st2=[]\n",
    "        while l1:\n",
    "            st1.append(l1.val)\n",
    "            l1=l1.next\n",
    "        while l2:\n",
    "            st2.append(l2.val)\n",
    "            l2=l2.next\n",
    "        carry=0\n",
    "        dummy=ListNode(0)\n",
    "        while st1 or st2 or carry:\n",
    "            v1=st1.pop() if st1 else 0\n",
    "            v2=st2.pop() if st2 else 0\n",
    "            sum=v1+v2+carry\n",
    "            carry=1 if sum>=10 else 0\n",
    "            sum=sum-10 if sum>=10 else sum\n",
    "            cur=ListNode(sum)\n",
    "            cur.next=dummy.next\n",
    "            dummy.next=cur\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self,head:Optional[ListNode]):\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        new_head=self.reverseList(head.next)\n",
    "        head.next.next=head\n",
    "        head.next=None\n",
    "        return new_head\n",
    "    \n",
    "    def addTwo(self,l1:Optional[ListNode],l2:Optional[ListNode],c=0):\n",
    "        if l1 is None and l2 is None:\n",
    "            return ListNode(c) if c else None\n",
    "        if l1 is None:\n",
    "            l1,l2=l2,l1\n",
    "        c+=l1.val+(l2.val if l2 else 0)\n",
    "        l1.val=c%10\n",
    "        l1.next=self.addTwo(l1.next,l2.next if l2 else None,c//10)\n",
    "        return l1\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1,l2=self.reverseList(l1),self.reverseList(l2)\n",
    "        l3=self.addTwo(l1,l2)\n",
    "        return self.reverseList(l3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\r\n",
    "        s1 = \"\"\r\n",
    "        p = l1\r\n",
    "        while p:\r\n",
    "            s1 += str(p.val)\r\n",
    "            p = p.next\r\n",
    "        s2 = \"\"\r\n",
    "        p = l2\r\n",
    "        while p:\r\n",
    "            s2 += str(p.val)\r\n",
    "            p = p.next\r\n",
    "        s = str(int(s1) + int(s2))\r\n",
    "        dummy = ListNode()\r\n",
    "        p0 = dummy\r\n",
    "        for i in range(len(s)):\r\n",
    "            p = ListNode(val=int(s[i]))\r\n",
    "            p0.next = p\r\n",
    "            p0 = p\r\n",
    "        p0.next = None\r\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def _reverser(self, cur: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 迭代-反转\n",
    "        pred,cur = None,cur\n",
    "        while cur:\n",
    "            temp=cur.next\n",
    "            cur.next=pred\n",
    "            pred=cur\n",
    "            cur=temp\n",
    "        return pred\n",
    "\n",
    "    def _addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 迭代-两数相加\n",
    "        # sentienlle=cur=ListNode(next=l1)     # 这是错误的做法，并不是从新构造l1而是构造cur\n",
    "        sentienlle=cur=ListNode()\n",
    "        carry=0\n",
    "        while(l1 or l2 or carry):\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            cur.next = ListNode(carry%10)               # 构造cur\n",
    "            cur=cur.next\n",
    "            if l1:l1=l1.next\n",
    "            if l2:l2=l2.next\n",
    "            carry=carry//10\n",
    "        return sentienlle.next\n",
    "        \n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self._reverser(l1)\n",
    "        l2 = self._reverser(l2)\n",
    "        l1 = self._addTwo(l1, l2)\n",
    "        return self._reverser(l1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, cur: Optional[ListNode], pre: Optional[ListNode])-> Optional[ListNode]:\n",
    "        # 递归反转列表\n",
    "        if cur is None:\n",
    "            return pre\n",
    "        res = self.reverseList(cur.next, cur)\n",
    "        cur.next = pre\n",
    "        return res\n",
    "\n",
    "    def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 迭代两数相加\n",
    "        carry = 0\n",
    "        cur = dummy = ListNode()\n",
    "        while l1 or l2 or carry:\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            cur.next  = ListNode(carry % 10)\n",
    "            carry = carry // 10\n",
    "            cur = cur.next\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        return dummy.next\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverseList(l1, None)\n",
    "        l2 = self.reverseList(l2, None)\n",
    "        res = self.addTwo(l1, l2)\n",
    "        return self.reverseList(res, None)\n",
    "        \n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
